import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Administrator
 * Date: 2022-10-13
 * Time: 下午 17:09
 */
public class Demo1 {
    public static void main(String[] args) {
        int[] nums = new int[10001];
        nums[1] = 1;
        nums[2] = 2;

        for(int i = 3; i < nums.length; i++) {
            nums[i] = nums[i-1] + nums[i-2];
            nums[i] = nums[i] % 10000;
        }

        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            int n =scan.nextInt();
            String str = "";

            for(int  i = 0; i < n; i++) {
                int m = scan.nextInt();
                char[] ch = String.valueOf(nums[m]).toCharArray();
                if(ch.length ==  1) {
                    str += "000" + String.valueOf(nums[m]);
                }else if(ch.length ==  2) {
                    str += "00" + String.valueOf(nums[m]);
                }else if(ch.length ==  3) {
                    str += "0" + String.valueOf(nums[m]);
                }else {
                    str+=String.valueOf(nums[m]);
                }
            }

            System.out.println(str);

        }
}
